package dp;

import java.util.Arrays;

/**
 * @author pengfei.hpf
 * @date 2020/2/12
 * @verdion 1.0.0
 *
 * Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
 *
 * Note:
 *
 * Each of the array element will not exceed 100.
 * The array size will not exceed 200.
 *  
 *
 * Example 1:
 *
 * Input: [1, 5, 11, 5]
 *
 * Output: true
 *
 * Explanation: The array can be partitioned as [1, 5, 5] and [11].
 *  
 *
 * Example 2:
 *
 * Input: [1, 2, 3, 5]
 *
 * Output: false
 *
 * Explanation: The array cannot be partitioned into equal sum subsets.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CanPartition {

    //dp
//    public boolean canPartition(int[] nums) {
//        if(nums == null || nums.length < 2){
//            return false;
//        }
//        int sum = 0;
//        for(int i = 0; i < nums.length; i ++){
//            sum += nums[i];
//        }
//        if(sum %2 != 0){
//            return false;
//        }
//        sum = sum /2;
//        boolean[] dp = new boolean[sum + 1];
//        for(int i = 0; i < nums.length; i ++){
//            for(int j = sum; j>= 0; j --){
//                if(nums[i] <= j){
//                    dp[j] = dp[j] || dp[j - nums[i]] || nums[i] == j;
//                }
//                if(dp[sum]){
//                    return true;
//                }
//            }
//        }
//        return dp[sum];
//    }


    //dfs
    public boolean canPartition(int[] nums){
        if(nums == null || nums.length < 2){
            return false;
        }
        int sum = 0;
        for(int i = 0; i < nums.length; i ++){
            sum += nums[i];
        }
        if(sum %2 != 0){
            return false;
        }
        sum = sum /2;
        Arrays.sort(nums);
        return dfs(nums, nums.length - 1, sum, sum);
    }

    private boolean dfs(int[] nums, int index, int target, int pass){
        if(index < 0 || target < 0 || pass < 0){
            return false;
        }
        if(target == 0 || pass == 0){
            return true;
        }
        return dfs(nums, index - 1, target - nums[index], pass) || dfs(nums, index - 1, target, pass - nums[index]);
    }


    public static void main(String[] args){

        System.out.println((new CanPartition()).canPartition(new int[]{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}));
    }
}
